<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,100分)- 勾股数元组（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>如果3个正整数(a,b,c)满足a^2 &#43; b^2 &#61; c^2的关系&#xff0c;则称(a,b,c)为勾股数&#xff08;著名的勾三股四弦五&#xff09;&#xff0c;</p> 
<p>为了探索勾股数的规律&#xff0c;我们定义如果勾股数(a,b,c)之间两两互质&#xff08;即a与b&#xff0c;a与c&#xff0c;b与c之间均互质&#xff0c;没有公约数&#xff09;&#xff0c;则其为勾股数元组&#xff08;例如(3,4,5)是勾股数元组&#xff0c;(6,8,10)则不是勾股数元组&#xff09;。</p> 
<p>请求出给定范围[N,M]内&#xff0c;所有的勾股数元组。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>起始范围N&#xff0c;1 &lt;&#61; N &lt;&#61; 10000</p> 
<p>结束范围M&#xff0c;N &lt; M &lt;&#61; 10000</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>1. a,b,c请保证a &lt; b &lt; c,输出格式&#xff1a;a b c&#xff1b;</p> 
<p>2. 多组勾股数元组请按照a升序&#xff0c;b升序&#xff0c;最后c升序的方式排序输出&#xff1b;</p> 
<p>3. 给定范围中如果找不到勾股数元组时&#xff0c;输出”NA“。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;"> <p>1</p> <p>20</p> </td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3 4 5<br /> 5 12 13<br /> 8 15 17</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>[1,20]范围内勾股数有&#xff1a;(3 4 5)&#xff0c;(5 12 13)&#xff0c;(6 8 10)&#xff0c;(8 15 17)&#xff0c;(9 12 15)&#xff0c;(12 16 20)&#xff1b;</p> <p>其中&#xff0c;满足(a,b,c)之间两两互质的勾股数元组有&#xff1a;(3 4 5)&#xff0c;(5 12 13)&#xff0c;(8 15 17);</p> <p>按输出描述中顺序要求输出结果。</p> </td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:85px;">输入</td><td style="width:413px;"> <p>5</p> <p>10</p> </td></tr><tr><td style="width:85px;">输出</td><td style="width:413px;">NA</td></tr><tr><td style="width:85px;">说明</td><td style="width:413px;"> <p>[5,10]范围内勾股数有&#xff1a;(6 8 10)&#xff1b;</p> <p>其中&#xff0c;没有满足(a,b,c)之间两两互质的勾股数元组&#xff1b;</p> <p>给定范围中找不到勾股数元组&#xff0c;输出”NA“</p> </td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题首先需要找出给定区间内的所有勾股数&#xff0c;当找出勾股数后&#xff0c;继续判断勾股数两两之间是否互质&#xff0c;若否&#xff0c;则丢弃&#xff0c;若是&#xff0c;则保留。</p> 
<p>最终保留的就是勾股数元组。</p> 
<p></p> 
<p>因此本题难点有二&#xff1a;1、如何找出所有勾股数&#xff1b; 2、如何判断两个数互质</p> 
<p>关于1&#xff0c;我们可以先求出区间[n,m]的所有数的平方&#xff0c;缓存到一个数组arr中&#xff0c;然后对该数组进行双重for遍历&#xff0c;外层遍历所有元素arr[i]&#xff0c;内层遍历i之后的每一个元素arr[j]&#xff0c;我们求arr[i]&#43;arr[j]的和sum&#xff0c;看arr中是否包含sum元素&#xff0c;若是&#xff0c;则就得到一组勾股数sqrt(arr[i])、sqrt(arr[j])、sqrt(sum)。</p> 
<p>按照上面逻辑求得所有勾股数。</p> 
<p>之后&#xff0c;我们可以根据辗转相除法判断两个数是否互质&#xff0c;比如求9和12是否互质&#xff0c;以及求47和18是否互质。</p> 
<p>我们只需要用</p> 
<p>a % b 得到一个 mod</p> 
<p>然后将</p> 
<p>a &lt;&#61; b</p> 
<p>b &lt;&#61; mod</p> 
<p>如果进行到b&#61;&#61;&#61;0时&#xff0c;则看此时a的值&#xff0c;若a&#61;&#61;&#61;1&#xff0c;则说明初始时的a,b互质&#xff0c;否则就有最大公约数结束时的a。</p> 
<p>如下图所示&#xff1a;</p> 
<p><img alt="" height="422" src="https://img-blog.csdnimg.cn/97ad5be8674342c085066ca8ea8fc5a1.png" width="499" /></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 2) {
    const [n, m] &#61; lines.map(Number);

    getResult(n, m);

    lines.length &#61; 0;
  }
});

function getResult(n, m) {
  const arr &#61; [];

  for (let i &#61; n; i &lt;&#61; m; i&#43;&#43;) {
    arr.push(i * i);
  }

  const set &#61; new Set(arr);

  const res &#61; [];
  for (let i &#61; 0; i &lt; arr.length; i&#43;&#43;) {
    for (let j &#61; i &#43; 1; j &lt; arr.length; j&#43;&#43;) {
      /* 判断勾股数 a^2 &#43; b^2 &#61; c^2 */
      const sum &#61; arr[i] &#43; arr[j];
      if (set.has(sum)) {
        res.push([Math.sqrt(arr[i]), Math.sqrt(arr[j]), Math.sqrt(sum)]);
      }
    }
  }

  const ans &#61; res.filter((group) &#61;&gt; {
    const [a, b, c] &#61; group;
    return (
      isRelativePrime(a, b) &amp;&amp; isRelativePrime(a, c) &amp;&amp; isRelativePrime(b, c)
    );
  });

  if (!ans.length) return console.log(&#34;NA&#34;);

  ans.forEach((g) &#61;&gt; console.log(g.join(&#34; &#34;)));
}

/* 判断两个数是否互质&#xff0c;辗转相除 */
function isRelativePrime(x, y) {
  while (y &gt; 0) {
    let mod &#61; x % y;
    x &#61; y;
    y &#61; mod;
  }

  return x &#61;&#61;&#61; 1;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);
    int n &#61; sc.nextInt();
    int m &#61; sc.nextInt();

    getResult(n, m);
  }

  public static void getResult(int n, int m) {
    ArrayList&lt;Integer&gt; arr &#61; new ArrayList&lt;&gt;();

    for (int i &#61; n; i &lt;&#61; m; i&#43;&#43;) {
      arr.add(i * i);
    }

    HashSet&lt;Integer&gt; set &#61; new HashSet&lt;&gt;(arr);
    ArrayList&lt;Integer[]&gt; res &#61; new ArrayList&lt;&gt;();

    for (int i &#61; 0; i &lt; arr.size(); i&#43;&#43;) {
      for (int j &#61; i &#43; 1; j &lt; arr.size(); j&#43;&#43;) {
        // 判断勾股数 a^2 &#43; b^2 &#61; c^2
        int sum &#61; arr.get(i) &#43; arr.get(j);
        if (set.contains(sum)) {
          res.add(
              new Integer[] {
                (int) Math.sqrt(arr.get(i)), (int) Math.sqrt(arr.get(j)), (int) Math.sqrt(sum)
              });
        }
      }
    }

    List&lt;Integer[]&gt; collect &#61;
        res.stream()
            .filter(
                g -&gt;
                    isRelativePrime(g[0], g[1])
                        &amp;&amp; isRelativePrime(g[0], g[2])
                        &amp;&amp; isRelativePrime(g[1], g[2]))
            .collect(Collectors.toList());

    if (collect.size() &#61;&#61; 0) {
      System.out.println(&#34;NA&#34;);
    } else {
      for (Integer[] g : collect) {
        System.out.println(g[0] &#43; &#34; &#34; &#43; g[1] &#43; &#34; &#34; &#43; g[2]);
      }
    }
  }

  // 判断两个数是否互质&#xff0c;辗转相除
  public static boolean isRelativePrime(int x, int y) {
    while (y &gt; 0) {
      int mod &#61; x % y;
      x &#61; y;
      y &#61; mod;
    }

    return x &#61;&#61; 1;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">import math

# 输入获取
n &#61; int(input())
m &#61; int(input())


# 判断两个数是否互质&#xff0c;辗转相除
def isRelativePrime(x, y):
    while y &gt; 0:
        mod &#61; x % y
        x &#61; y
        y &#61; mod

    return x &#61;&#61; 1


# 算法入口
def getResult():
    arr &#61; []

    for i in range(n, m &#43; 1):
        arr.append(i * i)

    setArr &#61; set(arr)

    res &#61; []
    for i in range(len(arr)):
        for j in range(i &#43; 1, len(arr)):
            # 判断勾股数 a^2 &#43; b^2 &#61; c^2
            sumV &#61; arr[i] &#43; arr[j]
            if sumV in setArr:
                res.append([int(math.sqrt(arr[i])), int(math.sqrt(arr[j])), int(math.sqrt(sumV))])

    ans &#61; list(
        filter(lambda x: isRelativePrime(x[0], x[1]) and isRelativePrime(x[0], x[2]) and isRelativePrime(x[1], x[2]),
               res))

    if len(ans) &#61;&#61; 0:
        print(&#34;NA&#34;)
    else:
        for g in ans:
            print(&#34; &#34;.join(map(str, g)))


# 算法调用
getResult()
</code></pre> 
<p></p> 
<h3>更高效的求解互质勾股数组的方法</h3> 
<p>互质勾股数组存在如下定理&#xff1a;</p> 
<p><a href="https://zhuanlan.zhihu.com/p/300922469?utm_source&#61;QQ_article_bottom&amp;utm_id&#61;0" rel="nofollow" title="闲谈费马大定理 - 知乎 (zhihu.com)">闲谈费马大定理 - 知乎 (zhihu.com)</a></p> 
<p><img alt="" height="848" src="https://img-blog.csdnimg.cn/9a33fc83a759467eaba8e57302bbc37c.png" width="606" /></p> 
<p></p> 
<p>而本题要在范围[n, m]中选取出所有互质的勾股数元组&#xff0c;我们假设存在x, y&#xff0c;且&#xff08;x &gt; y&#xff09;可以推导出互质的勾股数三元组(a, b, c)</p> 
<p>其中&#xff1a;</p> 
<ul><li>a &#61; x^2 - y^2</li><li>b &#61; 2 * x * y</li><li>c &#61; x^2 &#43; y^2</li></ul> 
<p>而 n &lt;&#61; a,b &lt; c &lt;&#61; m</p> 
<p>因此&#xff0c;可以继续推导出x,y的取值范围&#xff1a;</p> 
<p>a &#43; c &#61; 2 * x^2 &lt;&#61; 2 * m</p> 
<blockquote> 
 <p>即 x &lt;&#61; sqrt(m)</p> 
</blockquote> 
<p>c - a &#61; 2 * y^2&#xff0c;其中c &gt; a&#xff0c;因此c - a &gt; 0</p> 
<blockquote> 
 <p>即 y &gt; 0</p> 
</blockquote> 
<p>而 x &gt; y&#xff0c;因此x,y取值范围是</p> 
<blockquote> 
 <p>0 &lt; y &lt; x &lt;&#61; sqrt(m)</p> 
</blockquote> 
<p>另外&#xff0c;想要通过x,y推导出的勾股数三元组a,b,c互质&#xff0c;则x,y必然互质&#xff0c;且x,y必然一个是奇数&#xff0c;一个是偶数。</p> 
<p></p> 
<h4>JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 2) {
    const [n, m] &#61; lines.map(Number);

    getResult(n, m);

    lines.length &#61; 0;
  }
});

function getResult(n, m) {
  const ans &#61; [];

  const k &#61; Math.ceil(Math.sqrt(m));

  for (let y &#61; 1; y &lt; k; y&#43;&#43;) {
    for (let x &#61; y &#43; 1; x &lt; k; x&#43;&#43;) {
      if (isRelativePrime(x, y) &amp;&amp; (x &#43; y) % 2 &#61;&#61; 1) {
        const a &#61; x * x - y * y;
        const b &#61; 2 * x * y;
        const c &#61; x * x &#43; y * y;

        if (a &gt;&#61; n &amp;&amp; b &gt;&#61; n &amp;&amp; c &lt;&#61; m) {
          ans.push(a &lt; b ? [a, b, c] : [b, a, c]);
        }
      }
    }
  }

  if (ans.length &gt; 0) {
    ans.sort((a, b) &#61;&gt;
      a[0] !&#61; b[0] ? a[0] - b[0] : a[1] !&#61; b[1] ? a[1] - b[1] : a[2] - b[2]
    );

    for (let arr of ans) {
      console.log(arr.join(&#34; &#34;));
    }
  } else {
    console.log(&#34;NA&#34;);
  }
}

/* 判断两个数是否互质&#xff0c;辗转相除 */
function isRelativePrime(x, y) {
  while (y &gt; 0) {
    let mod &#61; x % y;
    x &#61; y;
    y &#61; mod;
  }

  return x &#61;&#61;&#61; 1;
}
</code></pre> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);
    int n &#61; sc.nextInt();
    int m &#61; sc.nextInt();

    getResult(n, m);
  }

  public static void getResult(int n, int m) {
    ArrayList&lt;int[]&gt; ans &#61; new ArrayList&lt;&gt;();

    int k &#61; (int) Math.ceil(Math.sqrt(m));

    for (int y &#61; 1; y &lt; k; y&#43;&#43;) {
      for (int x &#61; y &#43; 1; x &lt; k; x&#43;&#43;) {
        if (isRelativePrime(x, y) &amp;&amp; (x &#43; y) % 2 &#61;&#61; 1) {
          int a &#61; x * x - y * y;
          int b &#61; 2 * x * y;
          int c &#61; x * x &#43; y * y;

          if (a &gt;&#61; n &amp;&amp; b &gt;&#61; n &amp;&amp; c &lt;&#61; m) {
            ans.add(a &lt; b ? new int[] {a, b, c} : new int[] {b, a, c});
          }
        }
      }
    }

    if (ans.size() &gt; 0) {
      ans.sort((a, b) -&gt; a[0] !&#61; b[0] ? a[0] - b[0] : a[1] !&#61; b[1] ? a[1] - b[1] : a[2] - b[2]);
      for (int[] arr : ans) {
        System.out.println(arr[0] &#43; &#34; &#34; &#43; arr[1] &#43; &#34; &#34; &#43; arr[2]);
      }
    } else {
      System.out.println(&#34;NA&#34;);
    }
  }

  // 判断两个数是否互质&#xff0c;辗转相除
  public static boolean isRelativePrime(int x, int y) {
    while (y &gt; 0) {
      int mod &#61; x % y;
      x &#61; y;
      y &#61; mod;
    }

    return x &#61;&#61; 1;
  }
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">import math

# 输入获取
n &#61; int(input())
m &#61; int(input())


# 判断两个数是否互质&#xff0c;辗转相除
def isRelativePrime(x, y):
    while y &gt; 0:
        mod &#61; x % y
        x &#61; y
        y &#61; mod

    return x &#61;&#61; 1


# 算法入口
def getResult():
    ans &#61; []

    k &#61; math.ceil(math.sqrt(m))

    for y in range(1, k):
        for x in range(y &#43; 1, k):
            # 互质勾股数
            if isRelativePrime(x, y) and (x &#43; y) % 2 &#61;&#61; 1:
                a &#61; x * x - y * y
                b &#61; 2 * x * y
                c &#61; x * x &#43; y * y

                if a &gt;&#61; n and b &gt;&#61; n and c &lt;&#61; m:
                    ans.append([a, b, c] if a &lt; b else [b, a, c])

    if len(ans) &gt; 0:
        ans.sort()
        for lst in ans:
            print(&#34; &#34;.join(map(str, lst)))
    else:
        print(&#34;NA&#34;)


# 算法调用
getResult()
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>